Hvorfor behandler en sortert matras raskere enn behandling av en usortert matrise?

Du er et offer for forutsigelse av grenen mislykkes.
Hva er grenprediksjon?
Tenk på et jernbanekryss:
Bilde av Mecanismo, via Wikimedia Commons. Brukes under CC-By-SA 3.0 lisensen.
Tenk for argumentets skyld at dette er tilbake på 1800-tallet - før langdistanse eller radiokommunikasjon.
Du er operatør av et kryss og du hører et tog komme. Du aner ikke hvilken vei det skal gå. Du stopper toget for å spørre sjåføren hvilken retning de vil. Og så setter du bryteren på riktig måte.
Togene er tunge og har mye treghet. Så det tar for alltid å starte opp og bremse.
Er det en bedre måte? Du gjetter hvilken retning toget vil gå!
Gjettet du riktig, fortsetter det.
Hvis du gjettet feil, vil kapteinen stoppe, sikkerhetskopiere og rope på deg for å snu bryteren. Da kan den starte på nytt den andre banen.
Hvis du gjetter riktig hver gang, trenger toget aldri å stoppe. Hvis du gjetter feil for ofte, bruker toget mye tid på å stoppe, sikkerhetskopiere og starte på nytt.
Tenk på en if-setning: På prosessornivå er det en greninstruksjon:
Du er prosessor og du ser en gren. Du aner ikke hvilken vei det vil gå. Hva gjør du? Du stopper utførelsen og venter til forrige instruksjon er fullført. Så fortsetter du på riktig vei.
Moderne prosessorer er kompliserte og har lange rørledninger. Så de tar for alltid å "varme opp" og "bremse ned".
Er det en bedre måte? Du gjetter hvilken retning grenen vil gå!
Hvis du gjettet riktig, fortsetter du å kjøre.
Hvis du gjettet feil, må du skylle rørledningen og rulle tilbake til grenen. Deretter kan du starte på nytt den andre banen.
Hvis du gjetter riktig hver gang, vil henrettelsen aldri måtte stoppe. Hvis du gjetter feil for ofte, bruker du mye tid på å stoppe, rulle tilbake og starte på nytt.
Dette er grenforutsigelse. Jeg innrømmer at det ikke er den beste analogien siden toget bare kunne signalisere retningen med et flagg. Men på datamaskiner vet ikke prosessoren hvilken retning en gren vil gå til siste øyeblikk.
Så hvordan vil du strategisk gjette for å minimere antall ganger toget må sikkerhetskopiere og gå ned den andre veien? Du ser på fortidens historie! Hvis toget går til venstre 99% av tiden, antar du å gå. Hvis det veksler, så veksler du gjetningene dine. Hvis det går en vei hver tredje gang, antar du det samme ...
Med andre ord, du prøver å identifisere et mønster og følge det. Dette er mer eller mindre hvordan grenprediktorer fungerer.
De fleste applikasjoner har veloppførte grener. Så moderne grenprediktorer vil vanligvis oppnå> 90% trefffrekvenser. Men når vi står overfor uforutsigbare grener uten gjenkjennelige mønstre, er grenprediktorer praktisk talt ubrukelige.
Videre lesing: "Branch predictor" artikkel på Wikipedia.
Som antydet ovenfra, er den skyldige denne if-uttalelsen:
hvis (data [c]> = 128)
sum + = data [c];
Legg merke til at dataene er jevnt fordelt mellom 0 og 255. Når dataene er sortert, vil omtrent første halvdel av iterasjonene ikke komme inn i if-setningen. Etter det vil de alle angi if-setningen.
Dette er veldig vennlig for grenprediktoren siden grenen fortløpende går i samme retning mange ganger. Selv en enkel metningsteller vil korrekt forutsi grenen bortsett fra de få iterasjonene etter at den bytter retning.
Rask visualisering:
T = gren tatt
N = gren ikke tatt
data [] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
gren = N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNTTTTTTTTTT ... TTTTTTTTTTT (lett å forutsi)
Imidlertid, når dataene er helt tilfeldige, blir grenprediktoren ubrukelig, fordi den ikke kan forutsi tilfeldige data. Dermed vil det sannsynligvis være rundt 50% feilspådommer (ikke bedre enn tilfeldig gjetting).
data [] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, ...
gren = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N ...
= TTNTTTTNTNNTTTN ... (helt tilfeldig - vanskelig å forutsi)
Så hva kan gjøres?
Hvis kompilatoren ikke er i stand til å optimalisere grenen til et betinget trekk, kan du prøve noen hacks hvis du er villig til å ofre lesbarhet for ytelse.
Erstatte:
hvis (data [c]> = 128)
sum + = data [c];
med:
int t = (data [c] - 128) >> 31;
sum + = ~ t & data [c];
Dette eliminerer grenen og erstatter den med noen bitvise operasjoner.
(Merk at dette hacket ikke er strengt ekvivalent med den opprinnelige if-setningen. Men i dette tilfellet er det gyldig for alle inngangsverdiene til data [].)
Referanser: Core i7 920 @ 3,5 GHz
C ++ - Visual Studio 2010 - x64 utgivelse
// Gren - Tilfeldig
sekunder = 11,777
// Gren - sortert
sekunder = 2,352
// Grenløs - Tilfeldig
sekunder = 2,564
// Grenfri - Sortert
sekunder = 2,587
Java - NetBeans 7.1.1 JDK 7 - x64
// Gren - Tilfeldig
sekunder = 10,93293813
// Gren - sortert
sekunder = 5,643797077
// grenløs -Tilfeldig
sekunder = 3.113581453
// Grenfri - Sortert
sekunder = 3,186068823
Observasjoner:
Med filialen: Det er stor forskjell mellom sorterte og usorterte data.
Med hackingen: Det er ingen forskjell mellom sorterte og usorterte data.
I C ++ tilfelle er hacket litt tregere enn med grenen når dataene blir sortert.
En generell tommelfingerregel er å unngå dataavhengig forgrening i kritiske sløyfer (som i dette eksemplet).
Oppdater:
GCC 4.6.1 med -O3 eller -ftree-vectorize på x64 er i stand til å generere et betinget trekk. Så det er ingen forskjell mellom sorterte og usorterte data - begge er raske.
(Eller noe raskt: for den allerede sorterte saken kan cmov være tregere, spesielt hvis GCC setter den på den kritiske banen i stedet for bare å legge til, spesielt på Intel før Broadwell, hvor cmov har 2 sykluser ventetid: gcc optimaliseringsflagg-O3 gjør koden tregere enn -O2)
VC ++ 2010 kan ikke generere betingede trekk for denne grenen selv under / Ox.
Intel C ++ Compiler (ICC) 11 gjør noe mirakuløst. Den bytter ut de to løkkene, og heiser den uforutsigbare grenen til den ytre sløyfen. Så det er ikke bare immun mot feilforutsigelser, det er også dobbelt så raskt som hva VC ++ og GCC kan generere! Med andre ord utnyttet ICC test-loop for å beseire referanseverdien ...
Hvis du gir Intel-kompilatoren den grenløse koden, vektoriserer den bare rett ut ... og er like rask som med grenen (med løkkeutvekslingen).
Dette viser at selv modne moderne kompilatorer kan variere vilt i deres evne til å optimalisere kode ...
|
Grenforutsigelse.
Med en sortert matrise er tilstandsdataene [c]> = 128 først falske for et verdistrikk, og blir deretter sant for alle senere verdier. Det er lett å forutsi. Med et usortert utvalg betaler du forgreningskostnaden.
|
Årsaken til at ytelsen forbedres drastisk når dataene sorteres, er at forutsigelsesstraff for grenen blir fjernet, som forklart vakkert i Mysticials svar.
Nå, hvis vi ser på koden
hvis (data [c]> = 128)
sum + = data [c];
vi kan finne at betydningen av denne spesielle hvis ... annet ... gren er å legge til noe når en tilstand er oppfylt. Denne typen grener kan enkelt transformeres til en betinget bevegelsesuttalelse, som vil bli samlet til en betinget bevegelsesinstruksjon: cmovl, i et x86-system. Grenen og dermed den potensielle forutsigelsesstraffen for grenen blir fjernet.
I C, og dermed C ++, er utsagnet, som vil kompilere direkte (uten optimalisering) til den betingede bevegelsesinstruksjonen i x86, den ternære operatøren ...? ...: .... Så vi omskriver utsagnet ovenfor til en tilsvarende:
sum + = data [c]> = 128? data [c]: 0;
Mens vi opprettholder lesbarheten, kan vi sjekke hastighetsfaktoren.
På en Intel Core i7-2600K @ 3,4 GHz og Visual Studio 2010 utgivelsesmodus er referanseverdien (format kopiert fra Mysticial):
x86
// Gren - Tilfeldig
sekunder = 8,885
// Gren - sortert
sekunder = 1,528
// Grenløs - Tilfeldig
sekunder = 3,716
// Grenfri - Sortert
sekunder = 3,71
x64
// Gren - Tilfeldig
sekunder = 11.302
// Gren - sortert
sekunder = 1.830
// Grenløs - Tilfeldig
sekunder = 2.736
// Grenfri - Sortert
sekunder = 2.737
Resultatet er robust i flere tester. Vi får stor fart når greneresultatet er uforutsigbart, men vi lider litt når det er forutsigbart. Når du bruker et betinget trekk, er ytelsen faktisk den samme uavhengig av datamønsteret.
La oss se nærmere på ved å undersøke x86-samlingen de genererer. For enkelhets skyld bruker vi to funksjoner max1 og max2.
max1 bruker den betingede grenen hvis ... ellers ...:
int max1 (int a, int b) {
hvis (a> b)
returnere a;
ellers
retur b;
}
max2 bruker den ternære operatøren ...? ...: ...:
int max2 (int a, int b) {
returnere a> b? a: b;
}
På en x86-64 maskin genererer GCC -S forsamlingen nedenfor.
: maks1
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl -8 (% rbp),% eax
jle .L2
movl -4 (% rbp),% eax
movl% eax, -12 (% rbp)
jmp .L4
.L2:
movl -8 (% rbp),% eax
movl% eax, -12 (% rbp)
.L4:
movl -12 (% rbp),% eax
permisjon
ret
: max2
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl% eax, -8 (% rbp)
cmovge -8 (% rbp),% eax
permisjon
ret
max2 bruker mye mindre kode på grunn av bruken av instruksjon cmovge. Men den virkelige gevinsten er at max2 ikke innebærer grenhopp, jmp, som vil ha en betydelig ytelsesstraff hvis det forutsagte resultatet ikke er riktig.
Så hvorfor fungerer et betinget trekk bedre?
I en typisk x86-prosessor er gjennomføringen av en instruksjon delt inn i flere trinn. Grovt sett har vi forskjellig maskinvare for å håndtere forskjellige stadier. Så vi trenger ikke å vente på at en instruksjon er ferdig for å starte en ny. Dette kalles rørledning.
I en forgreningssak bestemmes følgende instruksjon av den forrige, så vi kan ikke gjøre rørledning. Vi må enten vente eller forutsi.
I en betinget flyttesak,utførelsesbetinget bevegelsesinstruksjon er delt inn i flere trinn, men de tidligere trinnene som Fetch og Decode er ikke avhengig av resultatet av den forrige instruksjonen; bare de siste trinnene trenger resultatet. Dermed venter vi en brøkdel av en instruks utførelsestid. Dette er grunnen til at den betingede flyttingsversjonen er tregere enn grenen når spådommen er enkel.
Boken Computer Systems: A Programmer's Perspective, andre utgave forklarer dette i detalj. Du kan sjekke avsnitt 3.6.6 for instruksjoner om betinget bevegelse, hele kapittel 4 for prosessorarkitektur og avsnitt 5.11.2 for spesiell behandling for forutsigelser og misforutsigelser.
Noen ganger kan noen moderne kompilatorer optimalisere koden vår til montering med bedre ytelse, noen ganger kan noen kompilatorer ikke (koden det gjelder bruker Visual Studios opprinnelige kompilator). Å kjenne ytelsesforskjellen mellom en gren og et betinget trekk når det er uforutsigbart, kan hjelpe oss med å skrive kode med bedre ytelse når scenariet blir så komplisert at kompilatoren ikke kan optimalisere dem automatisk.
|
Hvis du er nysgjerrig på enda flere optimaliseringer som kan gjøres med denne koden, bør du vurdere dette:
Starter med den originale sløyfen:
for (usignert i = 0; i <100000; ++ i)
{
for (usignert j = 0; j  = 128)
sum + = data [j];
}
}
Med løkkeutveksling kan vi trygt endre denne sløyfen til:
for (usignert j = 0; j  = 128)
sum + = data [j];
}
}
Deretter kan du se at hvis betinget er konstant gjennom hele utførelsen av i-sløyfen, slik at du kan heise hvis ut:
for (usignert j = 0; j  = 128)
{
for (usignert i = 0; i <100000; ++ i)
{
sum + = data [j];
}
}
}
Deretter ser du at den indre sløyfen kan kollapses i ett enkelt uttrykk, forutsatt at flytepunktsmodellen tillater det (/ fp: raskt kastes, for eksempel)
for (usignert j = 0; j  = 128)
{
sum + = data [j] * 100000;
}
}
Den ene er 100.000 ganger raskere enn før.
|
Ingen av oss vil uten tvil være interessert i måter å identifisere kode som er problematisk for CPUens gren-prediktor. Valgrind-verktøyets cachegrind har en gren-prediktorsimulator, aktivert ved å bruke --branch-sim = yes-flagget. Å kjøre det over eksemplene i dette spørsmålet, med antall ytre sløyfer redusert til 10000 og kompilert med g ++, gir disse resultatene:
Sortert:
== 32551 == Filialer: 656,645,130 (656,609,208 cond + 35,922 ind)
== 32551 == Feilspådommer: 169.556 (169.095 cond + 461 ind)
== 32551 == Feil rate: 0,0% (0,0% + 1,2%)
Usortert:
== 32555 == Grener: 655,996,082 (655,960,160 cond + 35,922 ind)
== 32555 == Feilspådommer: 164 073 152 (164 072 692 cond + 460 ind)
== 32555 == Feil rate: 25,0% (25,0% + 1,2%)
Boring ned i linje-for-linje-utgang produsert av cg_annotate ser vi for den aktuelle løkken:
Sortert:
Bc Bcm Bi Bim
10,001 4 0 0 for (usignert i = 0; i <10000; ++ i)
. . . . {
. . . . // primær sløyfe
327,690,000 10,016 0 0 for (usignert c = 0; c  = 128)
0 0 0 0 sum + = data [c];
. . . . }
. . . . }
Usortert:
Bc Bcm Bi Bim
10,001 4 0 0 for (usignert i = 0; i <10000; ++ i)
. . . . {
. . . . // primær sløyfe
327,690,000 10,038 0 0 for (usignert c = 0; c  = 128)
0 0 0 0 sum + = data [c];
. . . . }
. . . . }
Dette lar deg enkelt identifisere den problematiske linjen - i usortert versjon forårsaker linjen if (data [c]> = 128) 164,050,007 feilforutsagte betingede grener (Bcm) under cachegrinds gren-prediktormodell, mens den bare forårsaker 10 006 i den sorterte versjonen .
Alternativt, på Linux, kan du bruke subsystem for ytelsestellere til å utføre den samme oppgaven, men med innfødt ytelse ved hjelp av CPU-tellere.
perf stat ./sumtest_sorted
Sortert:
Resultatstatistikk for './sumtest_sorted':
11808.095776 oppgaveklokke # 0.998 CPUer brukt
1062 kontekstbrytere # 0,090 K / sek
14 CPU-migrasjoner # 0,001 K / sek
337 sidefeil # 0,029 K / sek
26.487.882.764 sykluser # 2.243 GHz
41,025,654,322 instruksjoner # 1,55 insns per syklus
6.558.871.379 grener # 555.455 M / sek
567 204 filial-savner # 0,01% av alle filialer
11.827228330 sekunder gått
Usortert:
Opptredenmotstatistikk for './sumtest_unsorted':
28877.954344 oppgaveklokke # 0.998 CPUer brukt
2584 kontekstbrytere # 0,089 K / sek
18 CPU-migrasjoner # 0,001 K / sek
335 sidefeil # 0,012 K / sek
65.076.127.595 sykluser # 2.253 GHz
41.032.528.741 instruksjoner # 0.63 innlegg per syklus
6.560.579.013 grener # 227.183 M / sek
1 646 394 749 filial-savner # 25,10% av alle filialer
28.935500947 sekunder gått tid
Det kan også gjøre kildekodenotering med demontering.
perf record -e gren-savner ./sumtest_unsorted
perf annotate -d sumtest_unsorted
Prosent | Kildekode og demontering av sumtest_unsorted
------------------------------------------------
...
: sum + = data [c];
0,00: 400a1a: mov -0x14 (% rbp),% eax
39.97: 400a1d: mov% eax,% eax
5.31: 400a1f: mov -0x20040 (% rbp,% rax, 4),% eax
4,60: 400a26: cltq
0,00: 400a28: legg til% rax, -0x30 (% rbp)
...
Se ytelsesopplæringen for mer informasjon.
|
Jeg har nettopp lest opp dette spørsmålet og svarene, og jeg føler at det mangler et svar.
En vanlig måte å eliminere forutsigelse på grenene som jeg har funnet å fungere spesielt bra på administrerte språk, er en tabelloppslag i stedet for å bruke en gren (selv om jeg ikke har testet det i dette tilfellet).
Denne tilnærmingen fungerer generelt hvis:
det er et lite bord og blir sannsynligvis lagret i prosessoren, og
du kjører ting i en ganske tett løkke, og / eller prosessoren kan forhåndslaste dataene.
Bakgrunn og hvorfor
Fra et prosessorperspektiv er minnet ditt sakte. For å kompensere for forskjellen i hastighet, er det innebygd et par hurtigbuffere i prosessoren din (L1 / L2 cache). Så forestill deg at du gjør dine fine beregninger, og finn ut at du trenger et stykke minne. Prosessoren vil få sin 'last' -operasjon og laster minnestykket i hurtigbufferen - og bruker deretter hurtigbufferen til å gjøre resten av beregningene. Fordi minnet er relativt tregt, vil denne 'belastningen' redusere programmet ditt.
Som grenforutsigelse, ble dette optimalisert i Pentium-prosessorer: prosessoren spår at den må laste inn et stykke data og prøver å laste det inn i hurtigbufferen før operasjonen faktisk treffer hurtigbufferen. Som vi allerede har sett, går spådommer noen ganger veldig galt - i verste fall må du gå tilbake og faktisk vente på en minnebelastning, noe som vil ta evig tid (med andre ord: sviktende forutsigelse av grenen er dårlig, et minne belastning etter at en forutsigelse av en forgrening mislykkes er bare fryktelig!).
Heldigvis for oss, hvis minnetilgangsmønsteret er forutsigbart, vil prosessoren laste det i sin raske hurtigbuffer og alt er bra.
Det første vi trenger å vite er hva som er lite? Mens mindre generelt er bedre, er en tommelfingerregel å holde seg til oppslagstabeller som er <= 4096 byte i størrelse. Som en øvre grense: hvis oppslagstabellen din er større enn 64 000, er det sannsynligvis verdt å revurdere.
Å lage et bord
Så vi har funnet ut at vi kan lage et lite bord. Neste ting å gjøre er å få en oppslagsfunksjon på plass. Oppslagsfunksjoner er vanligvis små funksjoner som bruker et par grunnleggende heltalloperasjoner (og, eller, xor, skift, legg til, fjern og kanskje multipliser). Du vil ha innspillene dine oversatt av oppslagsfunksjonen til en slags "unik nøkkel" i tabellen din, som deretter bare gir deg svaret på alt arbeidet du ønsket å gjøre.
I dette tilfellet:> = 128 betyr at vi kan beholde verdien, <128 betyr at vi blir kvitt den. Den enkleste måten å gjøre det på er å bruke et 'OG': hvis vi beholder det, så OG det med 7FFFFFFF; hvis vi vil bli kvitt det, OG vi det med 0. Legg også merke til at 128 er en styrke på 2 - slik at vi kan fortsette og lage en tabell med 32768/128 heltall og fylle den med ett null og mye 7FFFFFFFF's.
Administrerte språk
Du lurer kanskje på hvorfor dette fungerer bra på administrerte språk. Tross alt kontrollerer administrerte språk grensene til matriser med en gren for å sikre at du ikke roter ...
Vel, ikke akkurat ... :-)
Det har vært ganske mye arbeid med å eliminere denne grenen for administrerte språk. For eksempel:
for (int i = 0; i  = 128)? c: 0;
}
// Test
DateTime startTime = System.DateTime.Now;
lang sum = 0;
for (int i = 0; i <100000; ++ i)
{
// Primær sløyfe
for (int j = 0; j  = 128. Det betyr at vi enkelt kan trekke ut en enkelt bit som vil fortelle oss om vi vil ha en verdi eller ikke: ved å skifte dataene til høyre 7 bits, vi sitter igjen med en 0-bit eller en 1-bit, og vi vil bare legge til verdien når vi har en 1-bit. La oss kalle denne biten "beslutningsbit".
Ved å bruke 0/1-verdien på avgjørelsesbiten som en indeks i en matrise, kan vi lage kode som vil være like rask, enten dataene er sortert eller ikke sortert. Koden vår vil alltid legge til en verdi, men når beslutningsbiten er 0, vil vi legge til verdien et sted vi ikke bryr oss om. Her er koden:
// Test
klokke_ start = klokke ();
lang lang a [] = {0, 0};
lang lang sum;
for (usignert i = 0; i <100000; ++ i)
{
// Primær sløyfe
for (usignert c = 0; c > 7);
a [j] + = data [c];
}
}
double elapsedTime = static_cast  (klokke () - start) / CLOCKS_PER_SEC;
sum = a [1];
Denne koden kaster bort halvparten av tilleggene, men har aldri en filforutsigelsesfeil. Det er utrolig raskere på tilfeldige data enn versjonen med en faktisk if-uttalelse.
Men i testingen min var en eksplisitt oppslagstabell litt raskere enn dette, sannsynligvis fordi indeksering i en oppslagstabell var litt raskere enn bitforskyvning. Dette viser hvordan koden min setter opp og bruker oppslagstabellen (fantasiløst kalt lut for "LookUp Table" i koden). Her er C ++ -koden:
// Erklær og fyll deretter i oppslagstabellen
int lut [256];
for (usignert c = 0; c <256; ++ c)
lut [c] = (c> = 128)? c: 0;
// Bruk oppslagstabellen etter at den er bygget
for (usignert i = 0; i <100000; ++ i)
{
// Primær sløyfe
for (usignert c = 0; c  verdi)
node = node-> pLeft;
ellers
node = node-> pRight;
dette biblioteket vil gjøre noe sånt som:
i = (x  verdi);
node = node-> link [i];
Her er en lenke til denne koden: Red Black Trees, Eternally Confuzzled
|
I sortert tilfelle kan du gjøre det bedre enn å stole på vellykket grenforutsigelse eller noe grenløst sammenligningstriks: Fjern grenen helt.
Faktisk er matrisen delt i en sammenhengende sone med data <128 og en annen med data> = 128. Så du bør finne partisjonspunktet med et dikotomisk søk ​​(ved hjelp av Lg (arraySize) = 15 sammenligninger), og deretter gjøre en rett akkumulering fra det punktet.
Noe som (ukontrollert)
int i = 0, j, k = arraySize;
mens (i > 1;
hvis (data [j]> = 128)
k = j;
ellers
jeg = j;
}
sum = 0;
for (; i > 1;
for (i = 0, k = arraySize; i  = 128? k: i) = j)
j = (i + k) >> 1;
for (sum = 0; i  = 128)
/ \
/ \
/ \
true / \ false
/ \
/ \
/ \
/ \
B) sum + = data [c]; C) for løkke eller utskrift ().
Uten forutsigelse av grenen ville følgende forekomme:
For å utføre instruksjon B eller instruksjon C, må prosessoren vente til instruksjon A ikke når til EX-trinn i rørledningen, da beslutningen om å gå til instruksjon B eller instruksjon C avhenger av resultatet av instruksjon A. Så rørledningen vil se slik ut.
når hvis tilstanden blir oppfylt:
Når hvis tilstanden returnerer falsk:
Som et resultat av å vente på resultatet av instruksjon A, er de totale CPU-syklusene brukt i ovennevnte tilfelle (uten grenforutsigelse, for både sant og usant) 7.
Så hva er grenforutsigelse?
Grenprediktor vil prøve å gjette hvilken vei en gren (en hvis-så-annet-struktur) vil gå før dette er kjent med sikkerhet. Det vil ikke vente på at instruksjon A kommer til EX-trinnet i rørledningen, men den vil gjette avgjørelsen og gå til den instruksjonen (B eller C i tilfelle vårt eksempel).
I tilfelle riktig gjetning ser rørledningen omtrent slik ut:
Hvis det senere blir oppdaget at gjetningen var feil, kastes de delvis utførte instruksjonene, og rørledningen starter på nytt med riktig gren, og medfører en forsinkelse.
Tiden som er bortkastet i tilfelle feilforutsigelse på en gren er lik antall trinn i rørledningen fra hentetrinnet til kjøringsstadiet. Moderne mikroprosessorer har en tendens til å ha ganske lange rørledninger slik at forsinkelsen av feil prediksjon er mellom 10 og 20 tidssykluser. Jo lenger rørledningen er, desto større er behovet for en god grenprediktor.
I OP-koden, den første gangen den betingede, har grenprediktoren ingen informasjon for å basere prediksjon, så første gang vil den tilfeldig velge neste instruksjon. Senere i for loop kan den basere spådommen på historien.
For en matrise sortert i stigende rekkefølge er det tre muligheter:
Alle elementene er mindre enn 128
Alle elementene er større enn 128
Noen starter nye elementer er mindre enn 128, og senere blir det større enn 128
La oss anta at prediktoren alltid vil anta den sanne grenen ved første løp.
Så i det første tilfellet vil det alltid være santgren siden historisk sett er alle dets spådommer korrekte.
I det andre tilfellet vil det i utgangspunktet forutsi feil, men etter noen iterasjoner vil det forutsi riktig.
I det tredje tilfellet vil det i utgangspunktet forutsi riktig til elementene er mindre enn 128. Deretter vil det mislykkes i noen tid og det riktige i seg selv når det ser svikt i grenforutsigelser i historien.
I alle disse tilfellene vil feilen være for mindre i antall, og som et resultat vil det bare noen få ganger trenge å forkaste de delvis utførte instruksjonene og starte på nytt med riktig gren, noe som resulterer i færre CPU-sykluser.
Men i tilfelle en tilfeldig usortert matrise, vil prediksjonen trenge å forkaste de delvis utførte instruksjonene og starte på nytt med riktig gren mesteparten av tiden og resultere i flere CPU-sykluser sammenlignet med den sorterte matrisen.
|
Et offisielt svar ville være fra
Intel - Unngå kostnadene ved feil prediksjon
Intel - Branch and Loop Reorganization to Prevent Mispredictions
Vitenskapelige artikler - grenforutsigelse dataarkitektur
Bøker: J.L. Hennessy, D.A. Patterson: Dataarkitektur: en kvantitativ tilnærming
Artikler i vitenskapelige publikasjoner: T.Y. Yeh, Y.N. Patt gjorde mange av disse på grenforutsigelser.
Du kan også se fra dette nydelige diagrammet hvorfor grenprediktoren blir forvirret.
Hvert element i den opprinnelige koden er en tilfeldig verdi
data [c] = std :: rand ()% 256;
slik at prediktoren vil bytte side når std :: rand () blåser.
På den annen side, når den er sortert, vil prediktoren først bevege seg i en tilstand av sterkt ikke tatt, og når verdiene endres til høy verdi, vil prediktoren i tre løp gjennom endring hele veien fra sterkt ikke tatt til sterkt tatt.
|
I samme linje (jeg tror dette ikke ble fremhevet av noe svar) er det godt å nevne at noen ganger (spesielt i programvare der ytelsen betyr noe - som i Linux-kjernen), kan du finne noen hvis uttalelser som følgende:
hvis (sannsynlig (alt_is_ok))
{
/* Gjør noe */
}
eller lignende:
hvis (usannsynlig (veldig_forutsigbar_tilstand))
{
/* Gjør noe */
}
Både sannsynlig () og usannsynlig () er faktisk makroer som defineres ved å bruke noe som GCCs __builtin_expect for å hjelpe kompilatoren med å sette inn prediksjonskode for å favorisere tilstanden med tanke på informasjonen som er gitt av brukeren. GCC støtter andre innebygde moduler som kan endre atferden til det kjørende programmet eller avgi instruksjoner på lavt nivå som å tømme hurtigbufferen osv. Se denne dokumentasjonen som går gjennom tilgjengelige GCCs innebygde innstillinger.
Normalt finnes denne typen optimaliseringer hovedsakelig i sanntidsapplikasjoner eller innebygde systemer der kjøringstiden betyr noe og det er viktig. Hvis du for eksempel ser etter en feiltilstand som bare skjer 1/10000000 ganger, hvorfor ikke informere kompilatoren om dette? På denne måten vil grenforutsigelsen forutsette at tilstanden er falsk.
|
Ofte brukte boolske operasjoner i C ++ produserer mange grener i det kompilerte programmet. Hvis disse grenene er inne i løkker og det er vanskelig å forutsi, kan de redusere utførelsen betydelig. Boolske variabler lagres som 8-biters heltall med verdien 0 for false og 1 for true.
Boolske variabler er forbestemt i den forstand at alle operatører som har boolske variabler som inngang, sjekker om inngangene har en annen verdi enn 0 eller 1, men operatører som har boolere som utgang, kan ikke produsere noen annen verdi enn 0 eller 1. Dette gjør operasjoner med Boolske variabler som input mindre effektive enn nødvendig.
Tenk på eksempel:
bool a, b, c, d;
c = a && b;
d = a || b;
Dette implementeres vanligvis av kompilatoren på følgende måte:
bool a, b, c, d;
hvis (a! = 0) {
hvis (b! = 0) {
c = 1;
}
annet {
gå til CFALSE;
}
}
annet {
KALSE:
c = 0;
}
hvis (a == 0) {
hvis (b == 0) {
d = 0;
}
annet {
gå til DTRUE;
}
}
annet {
GANG:
d = 1;
}
Denne koden er langt fra optimal. Grenene kan ta lang tid i tilfelle feilforutsigelser. De boolske operasjonene kan gjøres mye mer effektive hvis det med sikkerhet er kjent at operandene ikke har andre verdier enn 0 og 1. Årsaken til at kompilatoren ikke antar en slik antagelse er at variablene kan ha andre verdier hvis de ikke er initialisert eller kommer fra ukjente kilder. Ovennevnte kode kan optimaliseres hvis a og b er initialisert til gyldige verdier, eller hvis de kommer fra operatører som produserer boolsk utgang. Den optimaliserte koden ser slik ut:
røye a = 0, b = 1, c, d;
c = a & b;
d = a | b;
char brukes i stedet for bool for å gjøre det mulig å bruke bitvise operatorer (& og |) i stedet for de boolske operatorene (&& og ||). De bitvise operatørene er enkeltinstruksjoner som tar bare en klokkesyklus. OR-operatøren (|) fungerer selv om a og b har andre verdier enn 0 eller 1. AND-operatoren (&) og EXCLUSIVE OR-operatøren (^) kan gi inkonsekvente resultater hvis operandene har andre verdier enn 0 og 1.
~ kan ikke brukes til IKKE. I stedet,Du kan lage en boolsk IKKE på en variabel som er kjent for å være 0 eller 1 ved å XORere den med 1:
bool a, b;
b =! a;
kan optimaliseres for å:
røye a = 0, b;
b = a ^ 1;
a && b kan ikke erstattes med a & b hvis b er et uttrykk som ikke skal evalueres hvis a er falsk (&& vil ikke evaluere b, & vil). Likeledes en || b kan ikke erstattes med a | b hvis b er et uttrykk som ikke skal evalueres hvis a er sant.
Å bruke bitvise operatorer er mer fordelaktig hvis operandene er variabler enn hvis operandene er sammenligninger:
bool a; dobbel x, y, z;
a = x> y && z <5.0;
er optimalt i de fleste tilfeller (med mindre du forventer at && uttrykket vil generere mange feilforutsigelser på grener).
|
Det er sikkert!...
Grenforutsigelse gjør at logikken går langsommere på grunn av byttingen som skjer i koden din! Det er som om du går en rett gate eller en gate med mange svinger, helt sikkert kommer den rette til å gjøres raskere! ...
Hvis matrisen er sortert, er tilstanden din falsk i det første trinnet: data [c]> = 128, blir deretter en sann verdi for hele veien til enden av gaten. Slik kommer du raskere til slutten av logikken. På den annen side, ved å bruke en usortert matrise, trenger du mye dreining og behandling som gjør at koden din går saktere ...
Se på bildet jeg opprettet for deg nedenfor. Hvilken gate kommer til å bli ferdig raskere?
Så programmatisk forårsaker forutsigelse av grenen at prosessen blir tregere ...
Også på slutten er det godt å vite at vi har to typer forutsigelser om at hver kommer til å påvirke koden din annerledes:
1. Statisk
2. Dynamisk
Forutsigelse av statisk gren brukes av mikroprosessoren første gang
en betinget gren oppstår, og dynamisk forutsigelse av grenen er
brukes til vellykkede henrettelser av den betingede avdelingskoden.
For effektivt å skrive koden din for å dra nytte av disse
regler, når du skriver if-else eller bytter uttalelser, sjekk mest
vanlige saker først og arbeider gradvis ned til det minst vanlige.
Sløyfer krever ikke nødvendigvis noen spesiell bestilling av kode for
predikasjon av statisk gren, som bare tilstanden til loop-iteratoren
brukes normalt.
|
Dette spørsmålet er allerede blitt besvart utmerket mange ganger. Likevel vil jeg trekke gruppens oppmerksomhet til nok en interessant analyse.
Nylig ble dette eksemplet (veldig modifisert) også brukt som en måte å demonstrere hvordan et stykke kode kan profileres i selve programmet på Windows. Underveis viser forfatteren også hvordan man bruker resultatene til å bestemme hvor koden bruker mesteparten av tiden i både sortert og usortert tilfelle. Til slutt viser stykket også hvordan man bruker et lite kjent trekk ved HAL (Hardware Abstraction Layer) for å bestemme hvor mye feilforutsigelse som skjer i det usorterte tilfellet.
Lenken er her:
En demonstrasjon av selvprofilering
|
Som det som allerede har blitt nevnt av andre, er det som ligger bak mysteriet Branch Predictor.
Jeg prøver ikke å legge til noe, men forklarer konseptet på en annen måte.
Det er en kort introduksjon på wiki som inneholder tekst og diagram.
Jeg liker forklaringen nedenfor som bruker et diagram for å utdype Branch Predictor intuitivt.
I dataarkitektur er en grenprediktor en
digital krets som prøver å gjette hvilken vei en gren (f.eks. en
if-then-else struktur) vil gå før dette er kjent med sikkerhet. De
Formålet med grenprediktoren er å forbedre flyten i
instruksjonsrørledning. Grenprediktorer spiller en kritisk rolle i
oppnå høy effektiv ytelse i mange moderne rørledninger
mikroprosessorarkitekturer som x86.
Toveis forgrening implementeres vanligvis med et betinget hopp
instruksjon. Et betinget hopp kan enten "ikke tas" og fortsette
utførelse med den første grenen av kode som følger umiddelbart
etter det betingede hoppet, eller det kan "tas" og hoppe til en
et annet sted i programminnet der den andre koden er
lagret. Det er ikke kjent med sikkerhet om et betinget hopp vil være
tatt eller ikke tatt før tilstanden er beregnet og
betinget hopp har bestått gjennomføringstrinnet i instruksjonen
rørledning (se fig. 1).
Basert på det beskrevne scenariet, har jeg skrevet en animasjonsdemo for å vise hvordan instruksjonene utføres i en rørledning i forskjellige situasjoner.
Uten grenforutsigeren.
Uten grenforutsigelse, måtte prosessoren vente til
betinget hoppinstruksjon har bestått gjennomføringsstadiet før
neste instruksjon kan gå inn i hentetrinnet i rørledningen.
Eksemplet inneholder tre instruksjoner, og den første er en betinget hoppinstruksjon. De to sistnevnte instruksjonene kan gå inn i rørledningen til den betingede hoppinstruksjonen er utført.
Det vil ta ni tidssykluser før tre instruksjoner er fullført.
Bruk Branch Predictor og ikke ta et betinget hopp. La oss anta at spådommen ikke tarbetinget hopp.
Det vil ta 7 tidssykluser før tre instruksjoner er fullført.
Bruk Branch Predictor og ta et betinget hopp. La oss anta at spådommen ikke tar det betingede hoppet.
Det vil ta ni tidssykluser før tre instruksjoner er fullført.
Tiden som er bortkastet i tilfelle feilforutsigelse på en gren er lik
antall trinn i rørledningen fra hentetrinnet til
utføre scenen. Moderne mikroprosessorer har en tendens til å ha ganske lang tid
rørledninger slik at forsinkelsen av feil prediksjon er mellom klokken 10 og 20
sykluser. Som et resultat øker behovet for en å lage en rørledning lenger
mer avansert gren prediktor.
Som du ser ser det ut til at vi ikke har en grunn til ikke å bruke Branch Predictor.
Det er ganske enkel demo som klargjør den helt grunnleggende delen av Branch Predictor. Hvis disse gifene er irriterende, er du velkommen til å fjerne dem fra svaret, og besøkende kan også få live demo-kildekoden fra BranchPredictorDemo
|
Gren-prediksjon gevinst!
Det er viktig å forstå at feilaktig prediksjon ikke bremser programmene. Kostnaden for en savnet prediksjon er akkurat som om grenprediksjon ikke eksisterte, og du ventet på evaluering av uttrykket for å bestemme hvilken kode som skulle kjøres (ytterligere forklaring i neste avsnitt).
hvis (uttrykk)
{
// Kjør 1
} annet {
// Kjør 2
}
Når det er en if-else \ switch-setning, må uttrykket evalueres for å bestemme hvilken blokk som skal utføres. I samlingskoden som genereres av kompilatoren, settes inn betingede greninstruksjoner.
En greninstruksjon kan føre til at en datamaskin begynner å utføre en annen instruksjonsrekkefølge og dermed avvike fra standardoppførselen til å utføre instruksjoner i rekkefølge (dvs. hvis uttrykket er usant, hopper programmet over koden til if-blokken) avhengig av noen tilstand, som er uttrykket evaluering i vårt tilfelle.
Når det er sagt, prøver kompilatoren å forutsi resultatet før det faktisk blir evaluert. Det vil hente instruksjoner fra if-blokken, og hvis uttrykket viser seg å være sant, så fantastisk! Vi fikk tiden det tok å evaluere den og gjorde fremgang i koden; Hvis ikke, kjører vi feil kode, rørledningen skylles og riktig blokk kjøres.
Visualisering:
La oss si at du må velge rute 1 eller rute 2. Når du venter på at partneren din skal sjekke kartet, har du stoppet på ## og ventet, eller du kan bare velge rute1 og hvis du var heldig (rute 1 er riktig rute), da flott, du slapp å vente på at partneren din skulle sjekke kartet (du sparte tiden det ville tatt ham å sjekke kartet), ellers vil du bare slå tilbake.
Mens det å spyle rørledninger er super raskt, er det verdt det i dag å ta denne gamblingen. Forutsi sorterte data eller data som endres sakte er alltid enklere og bedre enn å forutsi raske endringer.
O Rute 1 / -------------------------------
/ | \ /
| --------- ## /
/ \ \
\
Rute 2 \ --------------------------------
|
På ARM er det ingen gren nødvendig, fordi hver instruksjon har et 4-biters tilstandsfelt, som tester (til null pris) noen av 16 forskjellige forskjellige forhold som kan oppstå i prosessorstatusregisteret, og om tilstanden på en instruksjon er falsk, instruksjonen hoppes over. Dette eliminerer behovet for korte grener, og det ville ikke være noen grenforutsigelse for denne algoritmen. Derfor vil den sorterte versjonen av denne algoritmen kjøre tregere enn den usorterte versjonen på ARM, på grunn av ekstra omkostninger ved sortering.
Den indre sløyfen for denne algoritmen vil se ut som følgende på ARM-monteringsspråket:
MOV R0, # 0 // R0 = sum = 0
MOV R1, # 0 // R1 = c = 0
ADR R2, data // R2 = addr til dataarray (legg denne instruksjonen utenfor ytre sløyfe)
.inner_loop // Etikett for indre sløyfe
LDRB R3, [R2, R1] // R3 = data [c]
CMP R3, # 128 // sammenlign R3 med 128
LEGG TIL R0, R0, R3 // hvis R3> = 128, så sum + = data [c] - ingen gren nødvendig!
LEGG TIL R1, R1, # 1 // c ++
CMP R1, #arraySize // sammenlign c til arraySize
BLT inner_loop // Gren til inner_loop hvis c  ());
for (usignert c = 0; c  = 128
sum = sum + data1 (j);
slutt
slutt
slutt
toc;
ExeTimeWithSorting = toc - tic;
Resultatene for ovennevnte MATLAB-kode er som følger:
a: Forløpt tid (uten sortering) = 3479.880861 sekunder.
b: Forløpt tid (med sortering) = 2377.873098 sekunder.
Resultatene av C-koden som i @GManNickG får jeg:
a: Forløpt tid (uten sortering) = 19,8761 sek.
b: Forløpt tid (med sortering) = 7,37778 sek.
Basert på dette ser det ut som MATLAB er nesten 175 ganger tregere enn C-implementeringen uten sortering og 350 ganger tregere med sortering. Med andre ord, effekten (av forutsigelse av grener) er 1,46x for MATLAB-implementering og 2,7x for C-implementeringen.
|
Antagelsen fra andre svar om at man trenger å sortere dataene er ikke riktig.
Følgende kode sorterer ikke hele matrisen, men bare segmenter med 200 elementer, og kjører dermed raskest.
Sortering av bare k-elementdeler fullfører forbehandlingen i lineær tid, O (n), i stedet for O (n.log (n)) tiden som trengs for å sortere hele matrisen.
# inkluderer 
# inkluderer 
# inkluderer 
int main () {
int data [32768]; const int l = størrelse på data / størrelse på data [0];
for (usignert c = 0; c  = 128)
sum + = data [c];
}
}
std :: cout << static_cast  (klokke () - start) / CLOCKS_PER_SEC << std :: endl;
std :: cout << "sum =" << sum << std :: endl;
}
Dette "beviser" også at det ikke har noe å gjøre med noen algoritmiske problemer som sorteringsrekkefølge, og det er faktisk grenforutsigelse.
|
Bjarne Stroustrups svar på dette spørsmålet:
Det høres ut som et intervjuspørsmål. Er det sant? Hvordan vet du? Det er en dårlig ide å svare på spørsmål om effektivitet uten å gjøre noen målinger, så det er viktig å vite hvordan man måler.
Så jeg prøvde med en vektor på en million heltall og fikk:
Allerede sortert 32995 millisekunder
Blandet 125944 millisekunder
Allerede sortert 18610 millisekunder
Blandet 133304 millisekunder
Allerede sortert 17942 millisekunder
Blandet 107858 millisekunder
Jeg løp det et par ganger for å være sikker. Ja, fenomenet er ekte. Min nøkkelkode var:
ugyldig kjøring (vektor  & v, const streng og etikett)
{
auto t0 = systemklokke :: nå ();
sorter (v.begin (), v.end ());
auto t1 = systemklokke :: nå ();
cout << etikett
<< duration_cast  (t1 - t0) .count ()
<< "millisekunder \ n";
}
ugyldig tst ()
{
vektor  v (1'000'000);
iota (v.begin (), v.end (), 0);
kjør (v, "allerede sortert");
std :: shuffle (v.begin (), v.end (), std :: mt19937 {std :: random_device {} ()});
løp (v, "blandet");
}
I det minste er fenomenet ekte med denne kompilatoren, standardbiblioteket og optimaliseringsinnstillingene. Ulike implementeringer kan og gir forskjellige svar. Faktisk gjorde noen en mer systematisk studie (et raskt nettsøk vil finne det), og de fleste implementeringer viser den effekten.
En årsak er forutsigelse av grenen: nøkkeloperasjonen i sorteringsalgoritmen er “if (v [i]  = 128. Det betyr at vi enkelt kan trekke ut en enkelt bit som vil fortelle oss om vi vil ha en verdi eller ikke: ved å skifte dataene til høyre 7 bits, vi sitter igjen med en 0-bit eller en 1-bit, og vi vil bare legge til verdien når vi har en 1-bit. La oss kalle denne biten "beslutningsbit".
Ved å bruke 0/1-verdien på avgjørelsesbiten som en indeks i en matrise, kan vi lage kode som vil være like rask, enten dataene er sortert eller ikke sortert. Koden vår vil alltid legge til en verdi, men når beslutningsbiten er 0, vil vi legge til verdien et sted vi ikke bryr oss om. Her er koden:
// Test
klokke_ start = klokke ();
lang lang a [] = {0, 0};
lang lang sum;
for (usignert i = 0; i <100000; ++ i)
{
// Primær sløyfe
for (usignert c = 0; c > 7);
a [j] + = data [c];
}
}
double elapsedTime = static_cast  (klokke () - start) / CLOCKS_PER_SEC;
sum = a [1];
Denne koden kaster bort halvparten av tilleggene, men har aldri en filforutsigelsesfeil. Det er utrolig raskere på tilfeldige data enn versjonen med en faktisk if-uttalelse.
Men i testingen min var en eksplisitt oppslagstabell litt raskere enn dette, sannsynligvis fordi indeksering i en oppslagstabell var litt raskere enn bitforskyvning. Dette viser hvordan koden min setter opp og bruker oppslagstabellen (fantasiløst kalt lut for "LookUp Table" i koden). Her er C ++ -koden:
// Erklær og fyll deretter i oppslagstabellen
int lut [256];
for (usignert c = 0; c <256; ++ c)
lut [c] = (c> = 128)? c: 0;
// Bruk oppslagstabellen etter at den er bygget
for (usignert i = 0; i <100000; ++ i)
{
// Primær sløyfe
for (usignert c = 0; c  verdi)
node = node-> pLeft;
ellers
node = node-> pRight;
dette biblioteket vil gjøre noe sånt som:
i = (x  verdi);
node = node-> link [i];
Det er en fin løsning og kanskje det vil fungere.
|
Svært aktivt spørsmål. Tjen 10 rykte for å svare på dette spørsmålet. Omdømmekravet hjelper deg med å beskytte dette spørsmålet mot spam og ikke-svar-aktivitet.
Er ikke svaret du leter etter? Bla gjennom andre spørsmål merket java c ++ ytelsesoptimalisering gren-prediksjon eller still ditt eget spørsmål.